NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part2/11680

Internet Message Format | 1996-08-05 | 2.7 KB

Path: kuhub.cc.ukans.edu!anh
From: [e-mail]
Newsgroups: comp.lang.c
Subject: Re: REQUEST: Recursive functions
Message-ID: <[e-mail]>
Date: 25 Mar 96 12:50:41 CST
References: <4h7lft$[e-mail]> <[e-mail]> <[e-mail]>
Organization: University of Kansas Academic Computing Services

A classic way to find one's way through a 2D maze is to always keep to the
right.  In other words, if you arrive at an intersection, turn right,
eventually you will find your way out.  Now if your maze's only exit is
the entrance you will come back to the entrance after you have visited
the whole maze, and, hence, you must have encountered the cheese on the
way.  If there are multiple exits, well, just make sure you mark the
entrance to know when to quit searching.

Recursive function calls tend to blow up the stack, unless of course, it
is tail recursion and it is guaranteed to be removed.

Now whether to implement the above algorithm with or withour recursion is
up to you.  Good luck!

Anh

In article <[e-mail]>, Lawrence Kirby <[e-mail]> writes:
> In article <[e-mail]>
>            [e-mail] "Tarang Deshpande" writes:
>
>>Michael Talmage wrote:
>>>
>>> I need some help to write a recursive function that will move a mouse through
>>> a maze to find some cheese at the end.  My instructor did not really teach us
>>> how to write recursive functions in class.  Any help will be appreciated.
>>>
>>
>>I'm not going to tell you the answer but here is a quick leson in
>>recursion.  First of all anything you do recursively can be done
>>using loops.  But using loops is more complicated and cumbersome whereas
>>recursion is more elegant and simple.
>
> In the relatively few cases that model well recursively that is true,
> otherwise it is not. This is somewhat language dependent but you are
> posting to comp.lang.c.
>
>> However this does not mean that
>>you should always use recusion because recursion make heavy use of the
>>stack and this can cause you to run out of memory.
>
> Even if the C language guaranteed tail-end recursion elimination you
> would still write iterative loops as loops.
>
>>What recusion does is to divide the problem into two or more parts.
>
> It defines the problem in terms of a simpler form of itself. It must
> eventually reach a point where the solution can be determined directly or
> some other termination condition for it to be valid (i.e. not continue
> on indefinitely).
>
> --
> -----------------------------------------
> Lawrence Kirby | [e-mail]
> Wilts, England | [e-mail]
> -----------------------------------------
>